package 剑指offer;

/**
 * @author zhangmin
 * @create 2021-12-01 11:13
 * 位运算
 */
public class day21_15_65 {
    /**==============================================================================================================================================
     * 剑指 Offer 15. 二进制中1的个数
     * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量)）。
     * n & (n - 1) 可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止。
     * */
    public int hammingWeight(int n) {
        int res=0;
        while (n!=0){
            n=n&(n-1);
            res++;
        }
        return res;
    }

    /**==============================================================================================================================================
     * 剑指 Offer 65. 不用加减乘除做加法
     * 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
     * a(i)代表 a 的二进制第 i 位,a(i)和b（i）相加的无进位和与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）
     * 无进位和 n：n=a⊕b  异或运算
     * 进位 c： c=a&b<<1 与运算然后左移一位
     * 循环求 n 和 c ，直至进位 c = 0；此时 s = n ，返回 n可。
     * */
    public int add(int a, int b) {
        //进位为0时跳出
        while (b!=0){
            int c=(a&b)<<1;
            a^=b;//a=非进位和
            b=c;
        }
        return a;
    }
}
